In recent years, as computers and the Internet have prevailed, it has become popular to digitize information and use it as a digital image in place of conventional silver halide photos and paper documents. Furthermore, along with the remarkable advance of image processing techniques, a digital image can be readily edited or tampered with using, e.g., a photo retouch tool or the like. For this reason, the originality of a digital image is lower than that of conventional silver halide photos and paper documents, and the digital image is weak as an evidence. Conventionally, photo images are used as evidence photos in insurance companies or as records of progresses of construction sites in construction companies. Hence, the admissibility of such photo images, i.e., the originality plays an important role. However, the loss of admissibility of photos as evidence due to their digitization poses a serious problem.
In general, the originality of a digital image is guaranteed by generating a digital signature using public key cryptography in a Hash value of a digital image, as disclosed in U.S. Pat. No. 5,499,294. This method can detect the presence/absence of tampering but cannot detect a tampered position.
By contrast, in another method, a specific pattern is embedded in the entire image as a digital watermark, and when that image is tampered with or edited, the embedded pattern is destroyed, thereby detecting a tampered position. As an example of such method, a specific image called a stamp image is embedded in the LSB of each pixel data of image data. For example, Japanese Patent Laid-Open No. 2001-24876 has proposed a method of specifying the embedded position of a stamp image in an image using a pseudo random number generated based on secret key information.
The security of such conventional detection method of a tampered position using a digital watermark is based on the condition that its algorithm or embedded pattern is secret. Therefore, if the algorithm or embedded pattern is known to a third party, even when a digital image has been tampered with, the digital image can be forged or falsified to hide such tampering. That is, in the method of embedding a stamp image in the LSBs, a person who knows its algorithm extracts and saves the stamp image in the LSBs, tampers with the image, and reads out and embeds again the saved stamp image in the LSBs of the tampered image data, thus getting away with forgery without ever being detected of tampering.
The method of determining the embedded position of a stamp image using a pseudo random number, as disclosed in Japanese Patent Laid-Open No. 2001-24876, can assure higher security than the aforementioned method that embeds a stamp image in the LSBs, since the embedded position depends on the pseudo random number. However, once the embedded position of the stamp image is known to a third party by calculating, e.g., the difference between an original image and digitally watermarked image, similar forgery is achieved.
In general, the security of digital watermarking is premised on that its algorithm is secret, and none of methods are secure after their algorithms are known to a third party.
The conventional detection method of a tampered position using a digital watermark detects a tampered position by always embedding a stamp image. For this reason, the stamp image must be saved on the side where that image is received and used. Since such stamp image requires a large data size unlike key information, a large memory size is required, resulting in poor efficiency. On the other hand, once the stamp image is known to a third party, an image is readily forged. Hence, a method that does not use any stamp image is demanded.
Furthermore, no conventional method has been proposed that can be securely used when a plurality of different images which have undergone an embedding process using an identical key and identical stamp image are cut and pasted. For example, an attack that decomposes a plurality of different images each having the same size into blocks each having the same size, and composites a single image by replacing blocks at identical positions will be examined. At this time, if respective images use an identical key and identical stamp image, tampering cannot be detected, and this attack succeeds. Against such attach, an embedding process using different keys or different stamp images for respective images may be used. However, use of different keys or different stamp images for respective images impairs the operability of a digital watermarking application. If an image which is suspected of tampering is found, a key or stamp image used to process that image must be specified first. When an image to be verified is largely tampered with and the original image is hard to estimate, or when images processed using different keys are compounded, it is difficult to specify an original image. That is, the key or stamp image to be used cannot often be determined.